// 售货员的难题 - TSP问题
// 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
// 各村庄之间的路程s(1<=s<=1000)是已知的
// 且A村到B村的路程，与B到A的路大多不同(有向带权图)
// 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，
// 假设商店所在的村庄为1
// 他不知道选择什么样的路线才能使所走的路程最短
// 请你帮他选择一条最短的路
// 测试链接 : https://www.luogu.com.cn/problem/P1171
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

// 卡空间是吧？绕一下！
const int MAXN = 19;
int start[MAXN];
int back[MAXN];
// 这个图中，其实是不算起始村的，其他村庄彼此到达的路径长度
int g[MAXN][MAXN];
// 不算起始村庄的
int dp[1 << MAXN][MAXN];
int n;

inline int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return f * x;
}

// s : 不包含起始村的
// i : 目前在哪个村
int f(int s, int i)
{   
    // 从 i 回到 0
    if(s == (1 << n) - 1) return back[i];
    if(dp[s][i] != -1) return dp[s][i];
    int ans = INT_MAX;
    for(int j = 0; j < n; ++j)
    {
        // 从 i 走到 j
        if((s & (1 << j)) == 0)
        {
            ans = min(ans, g[i][j] + f(s | (1 << j), j));
        }
    }
    dp[s][i] = ans;
    return ans;
}

int compute()
{
    int ans = INT_MAX;
    // 起始村无编号
    for(int i = 0; i < n; ++i)
    {
        // 起始村 -> i号村  +  i号村出发所有村子都走最终回到起始村
        ans = min(ans, start[i] + f(1 << i, i));
    }
    return ans;
}

// 初始化
void build()
{
    for(int s = 0; s < (1 << n); ++s)
    {
        for(int i = 0; i < n; ++i) dp[s][i] = -1;
    }
}

int main()
{
    n = read() - 1;
    read();  // 读取起始点到起始点的距离
    build();
    // 从起始点到 i
    for(int i = 0; i < n; ++i) start[i] = read();
    for(int i = 0; i < n; ++i)
    {
        back[i] = read(); // 从 i 回到起始点
        for(int j = 0; j < n; ++j)
        {
            g[i][j] = read();
        }
    }
    printf("%d\n", compute());

    return 0;
}